package edu.whu.rose.clock.kps.algorithm.blinks.index;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

import edu.whu.rose.clock.kps.graph.GraphMatrix;
import edu.whu.rose.clock.ssql.util.ExpandableIntArray;
import edu.whu.rose.clock.ssql.util.SequentialIntArray;

public class GraphPartition {

	private GraphMatrix graph;
	private int blocksize;

	private boolean[] signed;
	private int lastPosition;
	
	private int[] vertex_block;
	private int currentBlock;
	private int[] vertex_edgeseperator;
	
	int vnum = 0;
	
	public GraphPartition(GraphMatrix graph, int blocksize) {
		this.graph = graph;
		this.blocksize = blocksize;
	}
	
	public static void main(String[] args) {
		GraphMatrix graph = new GraphMatrix(198467);
		graph.loadEdges("F:/data/5000029_graph/edge.txt");
		
		GraphPartition gp = new GraphPartition(graph, 300);
		Block[] blocks = gp.process();
		int[][] edges = gp.findEdgeSeperator(blocks);
		HashMap<Integer, SequentialIntArray> portals = gp.producePortal(edges, blocks);
		SequentialIntArray sia = portals.get(49760);
		if (sia != null) {
			if (sia.binarySearch(306) != -1)
				System.out.println("yes");
		}
	}
	
	public Block[] process() {
		signed = new boolean[graph.getN()];
		vertex_block = new int[graph.getN()];
		vertex_edgeseperator = new int[graph.getN()];
//		ArrayList<HashSet<Integer>> blocks = searchBlocks();
		return searchBlocks();
	}
	
	public int getEdgeNum() {
		return graph.getM();
	}
	
	public int[] getVertexBlock() {
		return vertex_block;
	}
	
//	private int[][] searchBlocks() {
//	private ArrayList<HashSet<Integer>> searchBlocks() {
//		// initialize all vertexes
//		signed = new boolean[graph.getN()];
//		for (int i = 0; i < graph.getN(); i++) {
//			signed[i] = false;
//		}
//		
//		int blocknum = graph.getN() / blocksize + 1;
////		int[][] blocks = new int[blocknum][];
//		ArrayList<HashSet<Integer>> blocks = new ArrayList<HashSet<Integer>>(blocknum * 4 /3 + 1);
//		for (int i = 0; i < blocknum - 1; i++) {
//			currentBlock = i + 1;
////			blocks[i] = searchBlock();
//			blocks.add(searchBlock());
//		}
//		currentBlock = blocknum;
////		blocks[blocknum - 1] = new int[graph.getN() - (blocknum - 1) * blocksize];
//		HashSet<Integer> block = new HashSet<Integer>();
//		blocks.add(block);
//		int j = 0;
//		for (int i = 0; i < graph.getN(); i++) {
//			if (!signed[i]) {
////				blocks[blocknum - 1][j] = i + 1;
//				block.add(new Integer(i + 1));
//				j++;
//			}
//		}
//		
//		return blocks;
//	}
	
	private Block[] searchBlocks() {
		int blocknum = graph.getN() / blocksize + 1;
		Block[] blocks = new Block[blocknum];
		for (int i = 0; i < blocknum - 1; i++) {
			currentBlock = i + 1;
//			if (currentBlock == 661) {
//				System.out.print(true);
//			}
			blocks[i] = searchBlock();
			System.out.println("extracted block " + i + ": " + blocks[i].size());
		}
		currentBlock = blocknum;
		Block block = new Block(blocknum);
		blocks[blocknum - 1] = block;
		for (int i = 0; i < graph.getN(); i++) {
			if (!signed[i]) {
				addVertex(i + 1, block);
			}
		}
		
		return blocks;
	}
	
	private Block searchBlock() {
		Block block = new Block(currentBlock);
		
		int size = 0;
		HashSet<Integer> current = new HashSet<Integer>();
		HashSet<Integer> next = new HashSet<Integer>();
		while (size < blocksize) {
			int startVertex = findStartVertex();
			lastPosition = startVertex;
			current.add(startVertex);
			while (!current.isEmpty() && size + current.size() < blocksize) {
				Iterator<Integer> it = current.iterator();
				while (it.hasNext()) {
					Integer vertex = it.next();
					addVertex(vertex.intValue(), block);
					size++;
					
					int[] neighbors = graph.genNeighbors(vertex.intValue());
					for (int j = 0; j < neighbors.length; j++) {
						Integer othervertex = new Integer(neighbors[j]);
						if (!signed[neighbors[j] - 1] && !current.contains(othervertex)) {
							next.add(othervertex);
						}
					}
				}
				current = next;
				next = new HashSet<Integer>();
			}
			if (current.size() + size >= blocksize) {
				break;
			}
		}
		
		Iterator<Integer> it = current.iterator();
		while (it.hasNext() && size < blocksize) {
			Integer vertex = it.next();
			addVertex(vertex.intValue(), block);
			size++;
		}
		
		return block;
	}
	
	private int findStartVertex() {
		int i = lastPosition + 1;
		while (signed[i - 1]) {
			i++;
		}
		return i;
	}
	
	private void addVertex(int vertex, Block block) {
		block.addVertex(vertex);
		signed[vertex - 1] = true;
		vertex_block[vertex - 1] = currentBlock;
		vnum++;
	}
	
	public int[][] findEdgeSeperator(Block[] blocks) {
		ExpandableIntArray sources = new ExpandableIntArray();
		ExpandableIntArray ends = new ExpandableIntArray();
		int total = 0;
		int total2 = 0;
		
		for (int i = 0; i < graph.getN(); i++) {
			int source = i + 1;
			int sblock = vertex_block[source - 1];
			int[] temp = graph.getEnds(source);
			if (temp == null) {
				continue;
			}
			total += temp.length;
			for (int j = 0; j < temp.length; j++) {
				int end = temp[j];
				int eblock = vertex_block[end - 1];
				if (sblock != eblock) {
					sources.add(source);
					ends.add(end);
					vertex_edgeseperator[source - 1] ++;
					vertex_edgeseperator[end - 1] ++;
				}
				else {
					if (vertex_block[source - 1] == 0) {
						System.out.println();
					}
					blocks[vertex_block[source - 1] - 1].addEdge(source, end);
					total2++;
				}
			}
		}
		
		int[][] result = new int[2][];
		result[0] = sources.toArray();
		result[1] = ends.toArray();
		return result;
	}
	
	public HashMap<Integer, SequentialIntArray> producePortal(int[][] edges, Block[] blocks) {
		HashMap<Integer, SequentialIntArray> portals = new HashMap<Integer, SequentialIntArray>();
		for (int i = 0; i < edges[0].length; i++) {
			int source = edges[0][i];
			int end = edges[1][i];
			int portal = choosePortal(source, end, blocks);
			Integer P = new Integer(portal);
			SequentialIntArray blocklist = portals.get(P);
			if (blocklist == null) {
				blocklist = new SequentialIntArray();
				portals.put(P, blocklist);
			}
			if (portal == source) {
				vertex_edgeseperator[end - 1]--;
				blocks[vertex_block[end - 1] - 1].addEdge(source, end);
				blocks[vertex_block[end - 1] - 1].addVertex(source);
			}
			else {
				vertex_edgeseperator[source - 1]--;
				blocks[vertex_block[source - 1] - 1].addEdge(source, end);
				blocks[vertex_block[source - 1] - 1].addVertex(end);
			}
			blocks[vertex_block[source - 1] - 1].addPortal(portal);
			blocks[vertex_block[end - 1] - 1].addPortal(portal);
			blocklist.insert(vertex_block[source - 1]);
			blocklist.insert(vertex_block[end - 1]);
		}
		System.out.println("Total number of portals: " + portals.size());
		
		return portals;
	}
	
	private int choosePortal(int source, int end, Block[] blocks) {
		double parameter = 1.0d;
		double score1 = vertex_edgeseperator[source - 1] + parameter * blocks[vertex_block[source - 1] - 1].size();
		double score2 = vertex_edgeseperator[end - 1] + parameter * blocks[vertex_block[end - 1] - 1].size();
		if (score1 > score2) {
			return source;
		}
		else {
			return end;
		}
	}
	
//	private int[] searchBlock() {
//	private HashSet<Integer> searchBlock() {
////		int[] block = new int[blocksize];
//		HashSet<Integer> block = new HashSet<Integer>(blocksize * 4 / 3 + 1);
//		int size = 0;
//		SequentialIntArray current = new SequentialIntArray(blocksize);
//		SequentialIntArray next = new SequentialIntArray(blocksize);
//		while (size < blocksize) {
//			int startVertex = findStartVertex();
//			lastPosition = startVertex;
//			current.insert(startVertex);
//			while (current.getCapacity() > 0) {
//				for (int i = 0; i < current.getCapacity(); i++) {
//					size = addVertex(current.get(i), block, size);
//					int[] neighbors = graph.genNeighbors(current.get(i));
//					for (int j = 0; j < neighbors.length; j++) {
//						if (!signed[neighbors[j] - 1] && current.binarySearch(neighbors[j]) == -1) {
//							next.insert(neighbors[j]);
//						}
//					}
//				}
//				current = next;
//				if (current.getCapacity() + size > blocksize) {
//					break;
//				}
//				next = new SequentialIntArray(blocksize);
//			}
//			if (current.getCapacity() + size > blocksize) {
//				break;
//			}
//		}
//		
//		int rest = blocksize - size;
//		for (int i = 0; i < rest; i++) {
//			size = addVertex(current.get(i), block, size);
//		}
//		
//		return block;
//	}
//	
//	private int findStartVertex() {
//		int i = lastPosition + 1;
//		while (signed[i - 1]) {
//			i++;
//		}
//		return i;
//	}
	
//	private int addVertex(int vertex, int[] block, int size) {
//	private int addVertex(int vertex, HashSet<Integer> block, int size) {
////		block[size] = vertex;
//		block.add(new Integer(vertex));
//		signed[vertex - 1] = true;
//		vertex_block[vertex - 1] = currentBlock;
//		size++;
//		return size;
//	}
	
//	private int[][] findEdgeSeperator() {
//		ExpandableIntArray sources = new ExpandableIntArray();
//		ExpandableIntArray ends = new ExpandableIntArray();
//		
//		for (int i = 0; i < graph.getN(); i++) {
//			int source = i + 1;
//			int sblock = vertex_block[source - 1];
//			int[] temp = graph.getEnds(source);
//			if (temp == null) {
//				continue;
//			}
//			for (int j = 0; j < temp.length; j++) {
//				int end = temp[j];
//				int eblock = vertex_block[end - 1];
//				if (sblock != eblock) {
//					sources.add(source);
//					ends.add(end);
//					vertex_edgeseperator[source - 1] ++;
//					vertex_edgeseperator[end - 1] ++;
//				}
//			}
//		}
//		
//		int[][] result = new int[2][];
//		result[0] = sources.toArray();
//		result[1] = ends.toArray();
//		return result;
//	}
	
//	private int[] producePortal(int[][] edges, ArrayList<HashSet<Integer>> blocks) {
//		SequentialIntArray portals = new SequentialIntArray();
//		for (int i = 0; i < edges[0].length; i++) {
//			int source = edges[0][i];
//			int end = edges[1][i];
//			if (portals.binarySearch(source) != -1) {
//				vertex_edgeseperator[end - 1]--;
//				blocks.get(vertex_block[end - 1]).add(new Integer(source));
//			}
//			else {
//				if (portals.binarySearch(end) != -1) {
//					vertex_edgeseperator[source - 1]--;
//					blocks.get(vertex_block[source - 1]).add(new Integer(end));
//				}
//				else {
//					int portal = choosePortal(source, end, blocks);
//					portals.insert(portal);
//					if (portal == source) {
//						vertex_edgeseperator[end - 1]--;
//						blocks.get(vertex_block[end - 1]).add(new Integer(source));
//					}
//					else {
//						vertex_edgeseperator[source - 1]--;
//						blocks.get(vertex_block[source - 1]).add(new Integer(end));
//					}
//				}
//			}
//		}
//		return portals.getArray();
//	}
	
//	private int choosePortal(int source, int end, ArrayList<HashSet<Integer>> blocks) {
//		double parameter = 1.0d;
//		double score1 = vertex_edgeseperator[source - 1] + parameter * blocks.get(vertex_block[source - 1]).size();
//		double score2 = vertex_edgeseperator[end - 1] + parameter * blocks.get(vertex_block[end - 1]).size();
//		if (score1 > score2) {
//			return source;
//		}
//		else {
//			return end;
//		}
//	}
	
//	private void processPortal(int portal, int[][] edges, ArrayList<HashSet<Integer>> blocks) {
//		for (int i = 0; i < edges[0].length; i++) {
//			if (edges[0])
//		}
//	}

}
